use crate::manifest::Manifest;
use std::collections::{HashMap, HashSet, VecDeque};

/// Analyzes dependencies and returns a sequence of activation batches.
///
/// Each inner vector is a batch of plugins that can be activated in parallel.
/// The outer vector represents the sequence of these batches.
///
/// # Errors
///
/// Returns an error if a cyclic dependency is detected.
pub fn make_priority_sequence<'a>(
    manifests: &[&'a Manifest],
    already_activated: &HashSet<String>,
) -> Result<Vec<Vec<&'a Manifest>>, String> {
    let mut graph: HashMap<&'a str, Vec<&'a str>> = HashMap::new();
    let mut in_degree: HashMap<&'a str, i32> = HashMap::new();

    let manifest_names: HashSet<&str> = manifests.iter().map(|m| m.name.as_str()).collect();

    for m in manifests {
        let m_name = m.name.as_str();
        in_degree.entry(m_name).or_insert(0);
        for dep_name in m.dependencies.keys() {
            // Only consider dependencies that are part of the current activation batch.
            // Ignore dependencies that are already activated.
            if manifest_names.contains(dep_name.as_str()) && !already_activated.contains(dep_name) {
                graph.entry(dep_name.as_str()).or_default().push(m_name);
                *in_degree.entry(m_name).or_default() += 1;
            }
        }
    }

    let mut queue: VecDeque<&'a Manifest> = VecDeque::new();
    for m in manifests {
        if in_degree.get(m.name.as_str()).cloned().unwrap_or(0) == 0 {
            queue.push_back(m);
        }
    }

    let mut result = Vec::new();
    let mut count = 0;

    while !queue.is_empty() {
        let batch_size = queue.len();
        let mut current_batch = Vec::with_capacity(batch_size);

        for _ in 0..batch_size {
            let u_manifest = queue.pop_front().unwrap();
            current_batch.push(u_manifest);
            count += 1;

            if let Some(dependents) = graph.get(u_manifest.name.as_str()) {
                for v_name in dependents {
                    if let Some(degree) = in_degree.get_mut(v_name) {
                        *degree -= 1;
                        if *degree == 0 {
                            // Find the manifest corresponding to v_name
                            let v_manifest = manifests.iter().find(|m| m.name == *v_name).unwrap();
                            queue.push_back(v_manifest);
                        }
                    }
                }
            }
        }
        result.push(current_batch);
    }

    if count != manifests.len() {
        return Err("A cyclic dependency was detected".to_string());
    }

    Ok(result)
}
